-
מבחן AKS לראשוניות
כל מה שרצית לדעת על מבחן AKS לראשוניות:מבחן AKS לראשוניות הוא אלגוריתם דטרמיניסטי להוכחת ראשוניות שנוצר ופורסם על ידי מנינדרה אגרוול, ניראג' קיאל, וניטין סקסנה מהמכון ההודי לטכנולוגיה קנפור, ונקרא על שמם. האלגוריתם התפרסם ב-6 באוגוסט 2002, במאמרם "PRIMES is in P". החוקרים קיבלו שבחים רבים על עבודתם, כולל פרס גדל לשנת 2006 ופרס פולקרסון…
-
המשפט הקטן של פרמה
כל מה שרצית לדעת על המשפט הקטן של פרמה:בתורת המספרים, המשפט הקטן של פרמה קובע שלכל ראשוני p ולכל מספר שלם a, ההפרש a p − a {\displaystyle a^{p}-a} מתחלק ב-p, כלומר a p ≡ a ( mod p ) {\displaystyle \ a^{p}\equiv a{\pmod {p}}} .משפט אוילר מכליל את המשפט הקטן של פרמה, מאחר…
-
אלגוריתם מילר-רבין
כל מה שרצית לדעת על אלגוריתם מילר-רבין:אלגוריתם מילר-רבין (או 'רבין-מילר') Miller-Rabin, הוא אלגוריתם לבדיקת ראשוניות של מספר טבעי. הוא דומה למבחן פרמה לבדיקת ראשוניות אשר מבוסס על ההיפוך הלוגי של המשפט הקטן של פרמה, אך מרחיב אותו בצורה שמתגברת על מספרי קרמייקל – מקרי הקצה עבורם מבחן פרמה אינו עובד. הוכחת הנכונות של האלגוריתם דורשת…
-
משפט וילסון
כל מה שרצית לדעת על משפט וילסון:משפט וילסון הוא משפט בתורת המספרים, הקובע שאם p מספר ראשוני, אז p מחלק את (ראו עצרת למשמעות הסימון "!"). המשפט נקרא על-שם ג'ון וילסון, אף על פי שלגראנז' היה הראשון להוכיח את המשפט, בשנת 1773. הכיוון ההפוך למשפט נכון גם הוא, משום שפרט למקרה p=4, אם p אינו…